package getRow;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i));
        }
        return row;
    }
    // 1
    // 1 1
    // 1 2 1
    // 1 3 3 1
    // 1 4 6 4 1
    // 1 5 10 10 5 1
    // 1 6 15 20 15 6 1
}
//class Solution {
//    public List<Integer> getRow(int rowIndex) {
//        List<Integer> pre = new ArrayList<Integer>();
//        for (int i = 0; i <= rowIndex; ++i) {
//            List<Integer> cur = new ArrayList<Integer>();
//            for (int j = 0; j <= i; ++j) {
//                if (j == 0 || j == i) {
//                    cur.add(1);
//                } else {
//                    cur.add(pre.get(j - 1) + pre.get(j));
//                }
//            }
//            pre = cur;
//        }
//        return pre;
//    }
//}
//由组合数公式 \mathcal{C}_n^m=\dfrac{n!}{m!(n-m)!}C
//        n
//        m
//        ​
//        =
//        m!(n−m)!
//        n!
//        ​
//        ，可以得到同一行的相邻组合数的关系
//
//        \mathcal{C}_n^m= \mathcal{C}_n^{m-1} \times \dfrac{n-m+1}{m}
//        C
//        n
//        m
//        ​
//        =C
//        n
//        m−1
//        ​
//        ×
//        m
//        n−m+1
//        ​
//
//
//        由于 \mathcal{C}_n^0=1C
//        n
//        0
//        ​
//        =1，利用上述公式我们可以在线性时间计算出第 nn 行的所有组合数。